\documentclass[a4paper,oneside]{report}

\usepackage{lscape}
\usepackage{listings}
\usepackage{color}
\usepackage{multicol}
%\usepackage[left=2cm, right=2cm]{geometry} 

\newcommand{\code}[1]{\texttt{\#1}}

\lstset{ %
language=JAVA,                % choose the language of the code
basicstyle=\footnotesize,       % the size of the fonts that are used for the code
numbers=left,                   % where to put the line-numbers
numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
stepnumber=10,                   % the step between two line-numbers. If it's 1 each line will be numbered
numbersep=5pt,                  % how far the line-numbers are from the code
backgroundcolor=\color{white},  % choose the background color. You must add \usepackage{color}
showspaces=false,               % show spaces adding particular underscores
showstringspaces=false,         % underline spaces within strings
showtabs=false,                 % show tabs within strings adding particular underscores
frame=single,                    % adds a frame around the code
tabsize=2,                    % sets default tabsize to 2 spaces
captionpos=b,                   % sets the caption-position to bottom
breaklines=true,                % sets automatic line breaking
breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
escapeinside={\%*}{*)}          % if you want to add a comment within your code
}

\begin{document}
\input{../title.tex}
    
\section*{Report}
The approach solution to the problem was given:
\begin{itemize}
   \item Instruction selection.
   \item Mapping temporaries to the stack frame.
   \item Translating function calls and parameter references.
\end{itemize}

We selected the following MIPS instructions:
\begin{multicols}{2}
\lstinline|LABDEF Label| \(\to\) \lstinline|Label:| \newline

\lstinline|JUMP Label| \(\to\) \lstinline|b label| \newline

\lstinline|CJUMP relop src1 src2 label| 

(Depends on if we want to jump on true or false)

\quad \(\to\) \lstinline|bne| or \lstinline|beqz| \newline

\lstinline|STORE ty dst src| \(\to\) \lstinline|sb| or \lstinline|sw| \newline

\lstinline|EVAL dst exp| 

(Depends on the kind of exp)

\quad \lstinline|BINARY binop src1 src2| \(\to\) \lstinline|add| or \lstinline|div| or \lstinline|mul| or \lstinline|sub| \newline

\lstinline|ICON i| \(\to\) \lstinline|li| \newline

\lstinline|LABREF label| \(\to\) \lstinline|la| \newline

\lstinline|TEMPEXP temp| \(\to\) \lstinline|move| \newline
   
\lstinline|PROC label| \(\to\) \lstinline|.text label:| \newline

\lstinline|DATA label size| \(\to\) \lstinline|.data [.align 2] .space size| \newline

\lstinline|LOAD type temp1 temp2|  

(Depends on type)

\quad \(\to\) \lstinline|lb|  or \lstinline|lw|
	
\end{multicols}

We map temporaries to the stack frame as follows (see stack frame layout below):

\begin{lstlisting}
List<Temp> localList = prcDef.getLocals();
ListIterator localIter = localList.listIterator(localList.size());
counter = (localList.size() + 1) * 4;    //+1 since RV is also treated as a temp.
mipsOut.println("#[Allocate space for temps");
while(localIter.hasPrevious()){
    Temp local = (Temp)localIter.previous();
    mipsOut.println("    " + "li $t0, 4");
    mipsOut.println("    " + "sub $sp, $sp, $t0");				    
    symbolTable.put(local.toString(), counter + "($sp)");
    counter -= 4;
\end{lstlisting}

\noindent We use a symbol table to map each temporary to its stack address. \newline

To translate a function call we basically use the MIPS's instructions \lstinline|jal| for calling, and then \lstinline|jr| for returning (see calling conventions below for more details). Note that \lstinline|jal| automatically pass the return address in \lstinline|ra| \newline

To translate parameter references we push every parameter into the end of the caller's stack. Then each reference to the parameters in callee's body will be accessed by frame pointer according to parameters' offsets in the caller's stack.


\subsection*{Translation of control flow statements}
In the RTL code, there are two kinds of control flows. One is unconditional jump and the other is conditional jump. Based on the flag values, the conditional jumps could be classified by jumping when condition is true or false. When translating, we directly convert each jump statement into corresponding MIPS assembly code. The detail is listed in the follow:

\begin{multicols}{2}
\noindent Unconditional Jump
\begin{verbatim}
JUMP label

\end{verbatim}
\columnbreak
translates to:
\begin{verbatim}
b label

\end{verbatim}
\end{multicols}

\noindent The relative code
\lstinputlisting{code-fragments/jump.txt}	

\begin{multicols}{2}
\noindent Conditional True Jump
\begin{verbatim}
CJUMP true temp label



\end{verbatim}
\columnbreak
translates to:
\begin{verbatim}
lw $t0, addressOfTemp
li $t1, 0
bne $t0, $t1, label

\end{verbatim}
\end{multicols}

\noindent The relative code
\lstinputlisting{code-fragments/cjump_true.txt}	

\begin{multicols}{2}
\noindent Conditional False Jump
\begin{verbatim}
CJUMP false temp label

\end{verbatim}
\columnbreak
translates to:
\begin{verbatim}
lw $t0, addressOfTemp
beqz $t0, label

\end{verbatim}
\end{multicols}
\noindent The relative code
\lstinputlisting{code-fragments/cjump_false.txt}	

\subsection*{Mapping temporaries to registers}
We don't perform register allocation in this compiler. We recommend to to this in the future.
\subsection*{Layout of activation records (stack frames)}
We use the following layout for the stack frame:
\begin{verbatim}
	        --------------------------
        |   ...                  |
        |   Argument 2           |
        |   Argument 1           |
        |   Argument 0           | 4(fp)
    	    --------------------------
fp ->   |                        |
        |                        |
        |  local arrays          |
        |                        |
        |                        |
	        --------------------------
        | Old FP                 |
        | Old RA                 |
	        --------------------------
        |                        | n(sp)
        |                        |
        |   temp-variables       |
        |                        |
        |                        | 4(sp)
	        --------------------------
sp ->
\end{verbatim}
\subsection*{Calling convention}
We took the following decisions regarding to:
\begin{itemize}
	\item save and restore registers at function call
	\item access data on the stack
	\item pass arguments
	\item return result
	\item divide the work between caller and callee
\end{itemize}

We only have two registers to care about \lstinline|FP| and \lstinline|RA|. These are saved in the stack frame by the callee since it needs to use them. The callee should also restore them before return. \newline

To access data on the stack we use on of two registers as a base address: \lstinline|FP| and \lstinline|SP|. We use \lstinline|FP| to access arguments through \lstinline|FP + offset| and local variables through \lstinline|FP - offset|. \newline

We do not use any register for the arguments: all arguments are passed on the stack. \newline

We return the result via the \lstinline|v0| register. \newline

The work is divided between caller and callee as follows:

Caller:
\begin{itemize}
	\item (at the beginning)
	\item evaluate arguments and push them on the stack
	\item execute \lstinline|jal|
	\item (at the end)	
	\item pop arguments from stack
	\item pick up returned result from \lstinline|v0|
\end{itemize}

Callee:
\begin{itemize}
	\item allocate space on stack for the local arrays
    \item save \lstinline|FP| and \lstinline|RA| regs
    \item set \lstinline|FP| 
    \item place result in \lstinline|v0|
    \item restore \lstinline|FP| and \lstinline|RA| and \lstinline|SP| regs
    \item jump to address in \lstinline|ra| executing \lstinline|jr|
\end{itemize}

\newpage

    \section*{Code}
    
    Source code can be accessed at: \lstinline|/home/rogu1637/CompilerPrj/uC-compiler|
    
	We are using the supplied Java Framework. We mainly rewrote or defined the following classes :

	\subsection*{MIPS.java}
	\lstinputlisting{../../mips/MIPS.java}
    \newpage

\section*{Test Runs}
\subsection*{Output MIPS Code}
The test files quiet/parser/p08.c and quiet/rtl/r08.c are not existed, as a result, we only tested three other files whose output MIPS code list in the following section.
\subsubsection*{quiet/lexer/l05.c}
	\lstinputlisting{test-runs/l05.c.asm}	
\subsubsection*{quiet/rtl/r02.c}
	\lstinputlisting{test-runs/r02.c.asm}	
\subsubsection*{quiet/rtl/r05.c}
	\lstinputlisting{test-runs/r05.c.asm}	
	\newpage
\subsection*{Output from Programs Executed under SPIM}
We run the following programs on SPIM, and got their outputs. When running program of noisy/simple/sim07.c, It first printed out nothing. By checking the code, we found that a local variable "i" had not been initialized, but in uC, every variable should be explicitly initialized. After we adding the initialization, every thing went well.
\subsubsection*{noisy/simple/sim04.c}
	\lstinputlisting{test-runs/sim04.txt}	
	\subsubsection*{noisy/simple/sim06.c}
	\lstinputlisting{test-runs/sim06.txt}	
	\subsubsection*{noisy/simple/sim07.c}
	\lstinputlisting{test-runs/sim07.txt}	
	\subsubsection*{noisy/simple/sim10.c}
	\lstinputlisting{test-runs/sim10.txt}	
\subsubsection*{noisy/medium/fac.c}
	\lstinputlisting{test-runs/fac.txt}	
\subsubsection*{noisy/medium/fib.c}
	\lstinputlisting{test-runs/fib.txt}	
\subsubsection*{noisy/advanced/8queens.c}
	\lstinputlisting{test-runs/8queens.txt}
\subsubsection*{noisy/advanced/quick.c}
	\lstinputlisting{test-runs/quick.txt}

\end{document}
